import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * 链表实现队列:
 *      链表本身实现队列时， 复杂度会出现O(n), 多维护一个尾指针解决这个问题
 *      > 1. 入队时队列为空的处理    ☆
 *      > 2. 出队时，队列变空的处理  ☆
 *
 * @param <E> 泛型参数
 */
public class LinkedListQueue<E> implements Queue<E> {

    private class Node {
        public E elem;
        public Node next;

        public Node(E elem, Node next) {
            this.elem = elem;
            this.next = next;
        }

        public Node(E elem) { this(elem, null); }

        public Node() {  this(null, null); }

        @Override
        public String toString() { return elem.toString(); }
    }

    private Node head, tail; // 头尾指针
    private int size;        // 队列长度

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(E elem) {
        if (tail == null) { // 队列为空
            tail = new Node(elem, null);
            head = tail;
            size++;
            return;
        }

        // 队列不为空
        tail.next = new Node(elem, null);
        tail = tail.next; // 这里犯了错误，编码时时刻注意维护状态成员 ☆
        size++;
    }

    @Override
    public E dequeue() {
        if (size == 0) throw new NoSuchElementException("LinkedListQueue is empty");

        Node node = head;
        head = node.next;
        node.next = null;
        size--;

        if (head == null) tail = null;  // 此次出队为最后一个元素
        return node.elem;
    }

    @Override
    public E front() {
        if (size == 0) throw new NoSuchElementException("LinkedListQueue is empty");
        return head.elem;
    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("LinkedListQueue:\n");
        res.append(" > front[");
        for (Node cur = head; cur != null; cur = cur.next)
            res.append(cur.elem).append("->");
        res.append("NULL]tail");
        return res.toString();
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }
}
